package com.cjm.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Ti93 {
    public static void main(String[] args) {
        Ti93 ti93 = new Ti93();
        List<String> strings = ti93.restoreIpAddresses("25525511135");
        List<String> strings1 = ti93.restoreIpAddresses("0000");
        System.err.println("OK");
    }

    private List<String> res = new ArrayList<>();
    private LinkedList<String> path = new LinkedList<>();
    public List<String> restoreIpAddresses(String s) {
        method93(s, 0);
        return res;
    }

    private void method93(String s, int startIndex) {
        if (path.size() == 4) {
            List<String> xx = new ArrayList<>(path);
            Collections.reverse(xx);
            res.add(String.join(".", xx));
            return;
        }
        if (path.size() > 4) {
            return;
        }
        boolean flag = true;
        for (int i = startIndex+1; i <= s.length() && flag; i++) {
            String substring = "";
            if (path.size() == 3) {
                substring = s.substring(startIndex);
                flag = false;
            } else {
                substring =s.substring(startIndex, i);
            }
            if ((substring.length() > 1 && substring.startsWith("0")) || Long.parseLong(substring) > 255) {
                break;
            }
            path.addFirst(substring);
            method93(s, i);
            path.removeFirst();
        }
    }

}
